package com.zk.algorithm.linkedlist;

import com.zk.algorithm.bean.ListNode;

/**
 * @author zk
 */
public class RemoveDuplicateFromSortedList2 {

    // Input: 1->2->3->3->4->4->5
    // Output: 1->2->5
    //
    // Input: 1->1->1->2->3
    // Output: 2->3
    public ListNode deleteDuplicates(ListNode head) {
        // DUMMY -> 1 -> 1 -> 1 -> 2 -> 3
        //
        // use two pointers
        // slow: track the node before the dup nodes,
        // fast: to find the last node of dups.
        //
        ListNode dummy = new ListNode(0);
        dummy.next = head;

        // DUMMY -> 1 -> 1 -> 1 -> 2 -> 3
        //   ↑
        //          ↑
        ListNode fast = head,
                slow = dummy;

        while (fast != null) {
            // DUMMY -> 1 -> 1 -> 1 -> 2 -> 3
            //   ↑
            //  slow
            //
            //                    ↑
            //                  fast
            while (fast.next != null && fast.val == fast.next.val) {
                fast = fast.next;    //while loop to find the last node of the dups.
            }

            if (duplicateNodeDetected(fast, slow)) { //duplicates detected.
                // DUMMY    1 -> 1 -> 1 -> 2 -> 3
                //    ↑                    ^
                //  slow ------------------|
                //
                //                    ↑
                //                  fast
                slow.next = fast.next; //remove the dups.
                // DUMMY  ---------------> 2 -> 3
                //   ↑
                //  slow
                //                              ↑
                //                            fast
                fast = slow.next;     //reposition the fast pointer.
            } else { //no dup, move down both pointer.
                slow = slow.next;
                fast = fast.next;
            }

        }

        return dummy.next;
    }

    /**
     * 是否探测到了重复元素，正常情况下 slow -> fast
     *
     * @param fast
     * @param slow
     * @return
     */
    private boolean duplicateNodeDetected(ListNode fast, ListNode slow) {
        // DUMMY -> 1 -> 1 -> 1 -> 2 -> 3
        //                    ↑
        //                         ↑
        //                         ↑
        //                              ↑
        return slow.next != fast;
    }

}
